#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "DoubleLinkList.h"

#define true 1
#define false 0

//初始化
int DList_Init(DList* list)
{
    list->head = NULL;
    list->tail = NULL;
    list->len = 0;
    return true ;
}

//初始化，返回指针
DList* DList_Creat()
{
    DList* pDLidst = (DList*)malloc(sizeof(DList));
    if(pDLidst == NULL)
        return NULL;
    pDLidst->head = NULL;
    pDLidst->tail = NULL;
    pDLidst->len = 0;
    return pDLidst;
}

//创建节点
DNode* DList_CreateNode(ElementType element)
{
    DNode* NewNode = (DNode*) malloc(sizeof(DNode));
    if(NewNode == NULL)
    {
        printf("CreateNode malloc error!\n");
        return NULL;
    } 
    NewNode->data = element;
    NewNode->prev = NULL;
    NewNode->next = NULL;
    return NewNode;
}

//销毁双向链表
void DList_Destroy(DList* list, void (*DataDestroy)(ElementType))
{
    while(list->head != NULL)
    {
        DNode* freenode = list->head;
        list->head = list->head->next;
        DataDestroy(freenode->data);
        free(freenode);
    }
    list->head = NULL;
    list->tail = NULL;
    list->len =0;
}

//遍历
void DList_Travel(DList* list, void (*PrintCall)(ElementType))
{
    DNode* cur = list->head;
    while(cur != NULL)
    {
        if(PrintCall)
            PrintCall(cur->data);
        cur = cur->next;
    }
    printf("\n");
}

//尾插
void DList_InsertTail(DList* list, ElementType element)
{
    DNode* NewNode = DList_CreateNode(element);
    if(NewNode == NULL)
    {
        printf("DList_InsertTail create error!\n");
        return;
    } 
    if(list->len == 0)
    {
        list->head = NewNode;
        list->tail = NewNode;
    }
    else
    {
        list->tail->next = NewNode;
        NewNode->prev = list->tail;
        list->tail = NewNode;
    }
    list->len++;   
}

//头插
void DList_InsertHead(DList* list, ElementType element)
{
    DNode* NewNode = DList_CreateNode(element);
    if(NewNode == NULL)
    {
        printf("InsertHead create error!\n");
        return;
    } 
    if(list->len == 0)
    {
        list->head = NewNode;
        list->tail = NewNode;
    }
    else
    {
        list->head->prev = NewNode;
        NewNode->next = list->head;
        list->head = NewNode;
    }
    list->len++;
}

//按下标插入
DList* DList_InsertByIndex(DList* list, int index, ElementType element)
{
    if(list == NULL)
        printf("双向链表为空!\n");
    //头插
    DNode* NewNode = DList_CreateNode(element);
    if(index == 0)
    {
        NewNode->next = list->head;
        list->head->prev = NewNode;
        list->head = NewNode;
        list->len++;
    }
    else
    {
        DNode* cur = list->head;
        //找到要插入节点的前一个节点
        for(int i = 0; i < index - 1; ++i)
        {
            cur = cur->next;
        }
        //尾插
        if(cur->next == NULL)
        {
            cur->next = NewNode;
            NewNode->prev = cur;
            list->tail = NewNode;
            list->len++;
        }
        else
        {
            //下标位置插入
            cur->next->prev = NewNode;
            NewNode->next = cur->next;
            cur->next = NewNode;
            NewNode->prev = cur;
            list->len++;
        }
    }
    return list;
}

//尾删
void DList_PopBack(DList *list)
{
    DList_RemoveByIndex(list, list->len - 1);
}

//头删
void DList_PopFront(DList* list)
{
    DList_RemoveByIndex(list, 0);
}

//按位删除
void DList_RemoveByIndex(DList* list, int index)
{
    if(index < 0 || index > list->len)
    {
        printf("RemoveByIndex invalid space!\n");
        return;
    }
    //头删
    if(index == 0)
    {
        //只有一个节点 
       if(list->len == 1)
       {
           free(list->head);
           list->head = NULL;
           list->tail = NULL;
           list->len = 0;
           return;
       }
       //删除第一个节点
       DNode* freeNode = list->head;
       list->head = list->head->next;
       list->head->prev = NULL;
       free(freeNode);
       list->len--;
       return;
    }
    //尾删
    if(index == list->len - 1)
    {
       DNode* freeNode = list->tail;
       list->tail = list->tail->prev;
       list->tail->next = NULL;
       free(freeNode);
       list->len--;
       return;
    }
    //任意位置删除
    DNode* cur = list->head;
    //找到要删除节点的前一个节点
    while(index > 0)
    {
        cur = cur->next;
        index--;
    }
    DNode* PrevNode = cur->prev;
    DNode* NextNode = cur->next;
    PrevNode->next = cur->next;
    NextNode->prev = cur->prev;
    free(cur);
    list->len--;
}

//查找第一个值符合的元素
int DList_FindFirstByElement(DList* list, ElementType element, DataCompare dataCompare)
{
    int count = 0;
    DNode* cur = list->head;
    while(cur != NULL)
    {
        if(dataCompare(cur->data, element))
        {
            return count;
        }
        count++;
        cur = cur->next;
    }
    return -1;
}

//按值删除
void DList_RemoveByElement(DList* list, ElementType element, DataCompare dataCompare)
{
    int index = DList_FindFirstByElement(list, element, dataCompare);
    while(index != -1)
    {
        DList_RemoveByIndex(list, index);
        index = DList_FindFirstByElement(list, element, dataCompare);
    }
}

//查找下标所对应的值
ElementType DList_FindByIndex(DList* list, int index )
{
    if(list->len == 0)
    {
        printf("No data!\n");
    }
    DNode* cur = list->head;
    for(int i = 0; i < index; ++i)
    {
        cur = cur->next;
    }
    return cur->data;
}

//通过下标设定值
void DList_SetValueByIndex(DList* list, int index, ElementType element)
{
    DNode* cur = list->head;
    for(int i = 0; i < index; ++i)
    {
        cur = cur->next;
    }
    cur->data = element;
}

//更改元素值
void DList_SetValueByElement(DList* list, ElementType oldValue, ElementType newValue, DataCompare dataIsEqal)
{
    DNode* cur = list->head;
    while(cur != NULL)
    {
        if(dataIsEqal(cur->data, oldValue))
        {
            cur->data = newValue;
        }
        cur = cur->next;
    }
}



